package test.algorithm.FastSlowPointer;

import test.algorithm.FastSlowPointer.BinarySortTree.BiTNode;

public class AVLTree {
	
	class BiTNode{
		
		static final int LH = 1;
		static final int EH = 0;
		static final int RH = -1;
		
		private int data;
		
		private BiTNode parent;
		
		private BiTNode lChild;
		
		private BiTNode rChild;
		
		//平衡因子（值为-1、0、1，非这三个值必须要旋转，计算公式为左子树层次数减去右子树层次数）
		private int bf;
		
		public BiTNode(int data,int bf,BiTNode parent){
			this.data = data;
			this.bf = bf;
			this.parent = parent;
		}
		
	}
	
	//树的根节点
	private BiTNode root;
	
	/** 
     * 平衡而二叉树的插入操作 
     * 基本原理为： 
     * 1.首先如同二叉排序树一般，找到其要插入的节点的位置，并把元素插入其中； 
     * 2.自下向上进行回溯，回溯做两个事情： 
     * (1)其一是修改祖先节点的平衡因子，当插入 一个节点时只有根节点到插入节点 
     * 的路径中的节点的平衡因子会被改变，而且改变的原则是当插入节点在某节点(称为A) 
     * 的左子树 中时，A的平衡因子(称为BF)为BF+1,当插入节点在A的右子树中时A的BF-1， 
     * 而判断插入节点在左子树中还是右子树中只要简单的比较它与A的大小 
     * (2)在改变祖先节点的平衡因子的同时，找到最近一个平衡因子大于2或小于-2的节点， 
     * 从这个节点开始调整最小不平衡树进行旋转调整，关于如何调整见下文。 
     * 由于调整后，最小不平衡子树的高度与插入节点前的高度相同，故不需继续要调整祖先节点。 
     * 这里还有一个特殊情况，如果调整BF时，发现某个节点的BF变为0了，则停止向上继续调整， 
     * 因为这表明此节点中高度小的子树增加了新节点，高度不变，那么祖先节点的BF自然不变。 
     *  
     */  
	public boolean insert(int key){
		
		if(root==null){
			//树为空的时候，添加到根节点
			root = new BiTNode(key,0,null);
			return true;
		}
		
		
		//当前遍历的节点
		BiTNode curr = root;
		//要插入节点的父节点
		BiTNode parent = null;
		do{
			parent = curr;
			if(key<curr.data){
				// 往左子树找
				curr = curr.lChild;
			}else if(key>curr.data){
				// 往右子树找
				curr = curr.rChild;
			}else{
				// 找到，插入失败
				return false;
			}
		}while(curr!=null);
		
		
		//插入节点
		if(key<parent.data){
			//插入左孩子
			parent.lChild = new BiTNode(key,BiTNode.EH,parent);
		}else{
			//插入右孩子
			parent.rChild = new BiTNode(key,BiTNode.EH,parent);
		}
		
		//自下向上回溯，查找最近不平衡节点  
        while(parent!=null){
        	if(key<parent.data){
        		//插入节点在parent的左子树中
        		parent.bf++;
        	}else{
        		//插入节点在parent的右子树中
        		parent.bf--;
        	}
        	
        	if(parent.bf == BiTNode.EH){
        		//此节点的balance为0，不再向上调整BF值，且不需要旋转
        		break;
        	}
        	
        	if(Math.abs(parent.bf) == 2){
        		//找到最小不平衡子树根节点 ，旋转修复
        		fixAfterInsertion(parent);
        		break;
        	}
        	parent = parent.parent;
        }
		
		return true;
	}
	
	/** 
     * 调整的方法： 
     * 1.当最小不平衡子树的根(以下简称R)为2时，即左子树高于右子树： 
     * 如果R的左子树的根节点的BF为1时，做右旋； 
     * 如果R的左子树的根节点的BF为-1时，先左旋然后再右旋 
     *  
     * 2.R为-2时，即右子树高于左子树： 
     * 如果R的右子树的根节点的BF为1时，先右旋后左旋 
     * 如果R的右子树的根节点的BF为-1时，做左旋 
     *  
     * 至于调整之后，各节点的BF变化见代码 
     * 
     * 左旋：两节点顺时针旋转 （右孩子做根左旋）
     * 右旋：两节点逆时针旋转 （左孩子做根右旋）
     */ 
	private void fixAfterInsertion(BiTNode parent){
		
		//左子树层次深
		if(parent.bf == 2){
			leftBalance(parent);
		}
		
		//右子树层次深
		if(parent.bf == -2){
			rightBalance(parent);
		}
		
	}
	
	/** 
     * 做左平衡处理 
     * 平衡因子的调整如图： 
     * 
     * 
     *   情况1(rd的BF为1)   
     *         t                       rd 
     *       /   \                   /    \ 
     *      l    tr   左旋后右旋                     l       t 
     *    /   \       ------->    /  \       \ 
     *  ll    rd                ll   rdl     tr 
     *       /    
     *     rdl   
     *   
     *   
     *   情况2(rd的BF为0)
     *         t                       rd 
     *       /   \                   /    \ 
     *      l    tr   左旋后右旋                    l       t 
     *    /   \       ------->    /  \    /  \ 
     *  ll    rd                ll   rdl rdr  tr 
     *       /   \ 
     *     rdl  rdr 
     *      
     *   
     *  情况3(rd的BF为-1)  
     *         t                       rd 
     *       /   \                   /    \ 
     *      l    tr   左旋后右旋                     l       t 
     *    /   \       ------->    /       /  \ 
     *  ll    rd                ll       rdr  tr 
     *           \ 
     *          rdr 
     *      
     *  
     *  情况4(L等高)   
     *         t                         l 
     *       /       右旋处理                                     /    \ 
     *      l        ------>          ll     t 
     *    /   \                             / 
     *   ll   rd                           rd 
     *   
     */  
	private boolean leftBalance(BiTNode t){
		// 标记树的高度是否改变
		boolean taller = true;  
		
		BiTNode l = t.lChild;  
        switch (l.bf) {
        	
        	//左高，右旋调整,旋转后树的高度减小(左左情况,见图)
        	case BiTNode.LH : 
        		t.bf = BiTNode.EH;
        		l.bf = BiTNode.EH;
        		rotateRight(t);
        		break;
        		
        	//右高，分情况调整 (左右情况,见图)
        	case BiTNode.RH :
        		BiTNode rd = l.rChild;
        		//调整各个节点的BF
        		switch(rd.bf){
        			//参见方法注释情况1
        			case BiTNode.LH : 
        				t.bf = BiTNode.RH;
        				l.bf = BiTNode.EH;
        				break;
        				
        			//参见方法注释情况2
        			case BiTNode.EH :
        				t.bf = BiTNode.EH;
        				l.bf = BiTNode.EH;
        				break;
        			
        			//参见方法注释情况3 
        			case BiTNode.RH :
        				t.bf = BiTNode.EH;
        				l.bf = BiTNode.LH;
        				break;
        		}
        		
        		//先左旋再右旋
        		rd.bf = BiTNode.EH;  
                rotateLeft(t.lChild);  
                rotateRight(t);  
                break;
            
            //特殊情况4,这种情况在添加时不可能出现，
            //只在移除时可能出现，旋转之后整体树高不变
            //删除root的右孩子
        	case BiTNode.EH :
        		t.bf = BiTNode.LH;
        		l.bf = BiTNode.RH;
        		rotateRight(t);
        		taller = false;
        		break;
        }
        
        return taller;
	}
	
	/** 
     * 最小旋转子树的根节点 
     * 向右旋转之后，p移到p的右子节点处，p的左子树l变为最小旋转子树的根节点 
     * l的右子节点变为p的左节点、 
     * 例如:       p(2)                       l(-1) 
     *            /         右旋转         		    /    \ 
     *          l(0)       ------>         /     p(0) 
     *         /   \                      /      / 
     *       lL(0) lR(0)                lL(0)  lR(0)  
     */  
	private void rotateRight(BiTNode p){  
		System.out.println("绕"+p.data+"右旋");
		if(p!=null){
			BiTNode l = p.lChild;
			
			//p的父节点赋给l的父节点
			l.parent = p.parent;
			//把l的右节点lR作为p的左节点 
			p.lChild = l.rChild; 
			
			if(l.rChild!=null){
				l.rChild.parent = p;
			}
			
			if(p.parent==null){
				//p是根节点，重新设置根节点
				root = l;
			}else if(p.parent.rChild==p){
				 //p是父节点右子树的根节点，重新设置左子树的根节点
				 p.parent.rChild = l;
			}else{
				 //p是父节点左子树的根节点，重新设置左子树的根节点
				 p.parent.rChild = l;
			}
			
			//p为l的右子树  
			l.rChild = p; 
			//设置p的父节点为l 
            p.parent = l;
		}
		 
	}

	/** 
     * 最小旋转子树的根节点 
     * 向左旋转之后p移到p的左子树处，p的右子树B变为此最小子树根节点， 
     * B的左子树变为p的右子树 
     * 比如：                p(-2)                     r(1) 
     *              \        左旋转                           /   \ 
     *             r(0)     ---->       p(0)   \        
     *             /   \                   \    \ 
     *           rL(0)  rR(0)              rL(0) rR(0)  
     *  旋转之后树的深度之差不超过1 
     */  
	private void rotateLeft(BiTNode p){
		System.out.println("绕"+p.data+"左旋");
		if(p!=null){
			BiTNode r = p.rChild;
			//p的父节点赋给r的父节点
			r.parent = p.parent;
			//把r的左节点rR作为p的右节点
			p.rChild = r.lChild;
			
			
			if(r.lChild!=null){
				r.lChild.parent = p;
			}
			
			if (p.parent == null) 
				//p是根节点 ,r变为父节点，即B为父节点
                root = r;                 
            else if (p.parent.lChild == p)  
            	//p是左子节点 ,p的父节点的左子树为r 
                p.parent.lChild = r;        
            else                          
            	//如果p是右子节点  
                p.parent.rChild = r;   
			
			//p为r的左子树
			r.lChild = p;
			//设置p的父节点为r
			p.parent = r;
		}
		
	}
	
	
	/** 
     * 做右平衡处理 
     * 平衡因子的调整如图： 
     *  情况1(ld的BF为1)
     *           t                               ld 
     *        /     \                          /     \ 
     *      tl       r       先右旋再左旋                            t       r 
     *             /   \     -------->      /   \       \ 
     *           ld    rr                 tl   ldl      rr 
     *          /   
     *       ldl   
     *       
     *  情况2(ld的BF为0)      
     *           t                               ld 
     *        /     \                          /     \ 
     *      tl       r       先右旋再左旋                            t       r 
     *             /   \     -------->      /   \    /  \ 
     *           ld    rr                 tl   ldl  ldr rr 
     *          /  \ 
     *       ldl  ldr 
     *       
     *   情况3(ld的BF为-1)      
     *           t                               ld 
     *        /     \                          /     \ 
     *      tl       r       先右旋再左旋                            t       r 
     *             /   \     -------->      /        /  \ 
     *           ld    rr                 tl        ldr rr 
     *             \ 
     *             ldr 
     *       
     *    情况4(r的BF为0)     
     *           t                                  r 
     *             \          左旋                                                   /   \ 
     *              r        ------->           t      rr      
     *            /   \                          \ 
     *           ld   rr                         ld 
     *           
     */  
	private boolean rightBalance(BiTNode t){
		//记录树的层次变化
		boolean heightLower = true;
		BiTNode r = t.rChild;
		
		switch(r.bf){
			//左高，分情况调整(右左情况)
			case BiTNode.LH:
				BiTNode ld = r.lChild;
				//调整各个节点的BF
				switch(ld.bf){
					//参见方法注释情况1
					case BiTNode.LH :
						t.bf = BiTNode.EH;
						r.bf = BiTNode.RH;
						break;
					
					//参见方法注释情况2	
					case BiTNode.EH :
						t.bf = BiTNode.EH;
						r.bf = BiTNode.EH;
						break;
						
					//参见方法注释情况3
					case BiTNode.RH :
						t.bf = BiTNode.LH;
						r.bf = BiTNode.EH;
						break;
				}
				
				ld.bf = BiTNode.EH;  
	            rotateRight(t.rChild);  
	            rotateLeft(t);  
	            break;
	        
	        //右高，左旋调整（右右情况）
			case BiTNode.RH:
				t.bf = BiTNode.EH;
				r.bf = BiTNode.EH;
				rotateLeft(t);  
	            break;
	        
	        //特殊情况4  
		    case BiTNode.EH:
		    	 r.bf = BiTNode.LH;  
		         t.bf = BiTNode.RH;  
		         rotateLeft(t);  
		         heightLower = false;  
		         break; 
		}
		return heightLower;
	}
	
	/** 
     * 查找指定元素，如果找到返回其BiTNode对象，否则返回null 
     */
	public BiTNode search(int key){
		BiTNode node = root;
		while(node!=null){
			if(key==node.data){
				return node;
			}else if(key<node.data){
				node = node.lChild;
			}else{
				node = node.rChild;
			}
		}
		return null;
	}
	
	/** 
     * 平衡二叉树的移除元素操作 
     *  
     */  
    public boolean remove(int key){  
    	BiTNode e = search(key);  
        if(e!=null){  
            delete(e);  
            return true;  
        }  
        return false;  
    } 
    
    /**
     * 获取中序遍历节点node的直接后继节点
     * @param node
     * @return
     */
    public BiTNode successor(BiTNode node){
    	if(node==null){
    		return null;
    	}else if(node.rChild!=null){
    		//有右子树，那么右子树最小的节点是node的直接后继节点
    		BiTNode p = node.rChild;
    		while(p.lChild!=null){
    			p = p.lChild;
    		}
    		return p;
    	}else{
    		//没有右子树，且node的父节点左孩子，则node的父节点是直接后继节点
    		BiTNode p = node.parent;
    		
    		//如果t是p的右子树，则继续向上搜索其直接后继 
    		//(node和其父节点都可能是右孩子，因此循环查找)
    		BiTNode ch = node;
    		while(p != null && ch == p.rChild){
    			ch = p;  
                p = p.parent;
    		}
    		
    		return p;
    	}
    }
    
    private void delete(BiTNode p){
    	//如果p左右子树都不为空，找到其直接后继，替换p，
    	//之后p指向s，删除p其实是删除s
    	//(左右子树都不为空，用直接后继节点替换之)
        if (p.lChild != null && p.rChild != null) { 
        	 // 找直接后继节点（右子树最左节点）
        	 BiTNode s = successor(p);  
             p.data = s.data;  
             p = s;  
        }  
        
        BiTNode replacement = (p.lChild != null ? p.lChild : p.rChild);
        
        
        if (replacement != null){
        	//要删除的节点有一个孩子（replacement不为空）
        	//（两个孩子的情况用直接后继节点替换了，后继节点没有左孩）
        	replacement.parent = p.parent;
        	
        	if(p.parent==null){
        		//要删除的p是根节点，修改root值
        		root = replacement;
        	}else if (p == p.parent.lChild){    
        		//删除节点p是左孩子
                p.parent.lChild  = replacement;
        	}else{
        		//删除节点p是右孩子
        		p.parent.rChild = replacement;
        	}
        	
        	//p的指针清空,防止内存泄露
        	p.lChild = p.rChild = p.parent = null;     
        	
        	//这里更改了replacement的父节点，所以可以直接从它开始向上回溯 修复到平衡 
            fixAfterDeletion(replacement);
        }else if(p.parent == null){
        	//全树只有一个节点
        	root = null;
        }else{
        	//修复
        	fixAfterDeletion(p);
        	//删除p
        	if (p.parent != null) {  
                if (p == p.parent.lChild){  
                    p.parent.lChild = null;  
                }else if (p == p.parent.rChild){  
                    p.parent.rChild = null; 
                }
                p.parent = null;  
            }  
        }
    }
    
    /** 
     * 删除某节点p后的调整方法： 
     * 1.从p开始向上回溯，修改祖先的BF值，这里只要调整从p的父节点到根节点的BF值， 
     * 调整原则为，当p位于某祖先节点(简称A)的左子树中时，A的BF减1，当p位于A的 
     * 右子树中时A的BF加1。当某个祖先节点BF变为1或-1时停止回溯，这里与插入是相反的， 
     * 因为原本这个节点是平衡的，删除它的子树的某个节点并不会改变它的高度 
     *  
     * 2.检查每个节点的BF值，如果为2或-2需要进行旋转调整，调整方法如下文， 
     * 如果调整之后这个最小子树的高度降低了，那么必须继续从这个最小子树的根节点(假设为B)继续 
     * 向上回溯，这里和插入不一样，因为B的父节点的平衡性因为其子树B的高度的改变而发生了改变， 
     * 那么就可能需要调整，所以删除可能进行多次的调整。 
     *  
     */  
    public void fixAfterDeletion(BiTNode p){
    	//看最小子树调整后，它的高度是否发生变化，如果减小，继续回溯
    	boolean heightLower = true;
    	BiTNode t = p.parent;
    	
    	//自下向上回溯，查找不平衡的节点进行调整
    	while(t!=null && heightLower){
    		 /** 
             * 删除的节点是右子树，等于的话，必然是删除的某个节点的左右子树不为空的情况 
             * 例如：     	  10 
             *          /    \ 
             *         5     15 
             *       /   \ 
             *      3    6  
             * 这里删除5，是把6的值赋给5，然后删除6，这里6是p，p的父节点的值也是6。 
             * 而这也是右子树的一种 (删除节点必然引起改节点的父bf变化，)
             */
    		if(p.data<t.data){
    			//删除左子树节点
    			t.bf--;
    		}else{
    			t.bf++;
    		}
    		
    		//父节点经过调整平衡因子后，如果为1或-1，
    		//说明调整之前是0，现在删除一个后代，平衡因子为1或-1，
    		//不影响该树的整体平衡，停止回溯。
    		if(Math.abs(t.bf) == 1){     
                break;  
            } 
    		
    		BiTNode r = t;  
            //这里的调整跟插入一样  
            if(t.bf == 2){  
            	//左旋
                heightLower = leftBalance(r);  
            }else if(t.bf==-2){  
            	//右旋
                heightLower = rightBalance(r);  
            }  
            t = t.parent; 
    	}
    	
    }
    
    /**
	 * 中序遍历二叉排序树(排序)
	 */
	private void inOrderTraverse(BiTNode root){
		if(root!=null){
			//遍历左子树
			inOrderTraverse(root.lChild);
			
			System.out.print(root.data+" ");
			
			//遍历右子树
			inOrderTraverse(root.rChild);
		}
		
	}
	
	/**
	 * 中序遍历二叉排序树(排序)
	 */
	public void inOrderTraverse(){
		inOrderTraverse(root);
	}
	public static void main(String[] args) {
		AVLTree tree = new AVLTree(); 
		
		System.out.println("------添加------");  
        tree.insert(50);  
        System.out.print(50+" ");  
        tree.insert(66);  
        System.out.print(66+" ");  
        for(int i=0;i<10;i++){  
            tree.insert(i);  
        }  
        
        System.out.print("平衡二叉树中序遍历：");
        tree.inOrderTraverse();
        System.out.println();
        
        System.out.println("------删除------");  
        tree.remove(8);  
        tree.remove(50);  
        tree.remove(66); 
        
        System.out.print("平衡二叉树中序遍历：");
        tree.inOrderTraverse();
        System.out.println();
	}

}
